/*
 * @Author: szx
 * @Date: 2021-11-06 14:00:13
 * @LastEditTime: 2021-11-06 14:21:33
 * @Description:
 * @FilePath: \leetcode\100-199\120\120.cpp
 */
#include <iostream>
#include <vector>
using namespace std;
class Solution {
   public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> dp(triangle[triangle.size() - 1].size());
        dp[0] = triangle[0][0];

        for (int i = 1; i < triangle.size(); i++) {
            int n = triangle[i].size();
            for (int j = n - 1; j >= 0; j--) {
                if (j == 0) {
                    dp[j] = dp[j] + triangle[i][j];
                } else if (j == n - 1) {
                    dp[j] = dp[j - 1] + triangle[i][j];
                } else {
                    dp[j] = triangle[i][j] + min(dp[j - 1], dp[j]);
                }
            }
        }
        int res = INT_MAX;
        for (int i : dp) {
            if (i < res) {
                res = i;
            }
        }
        return res;
    }
};
int main() { return 0; }